package com.note.feng.leetcode.algorithms.easy.ten;

import java.util.Arrays;

public class ThousandFive {
    /**
     * 1005 K 次取反后最大化的数组和
     * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
     *
     * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
     * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
     *
     * 以这种方式修改数组后，返回数组 可能的最大和 。
     *
     * 示例 1：
     *
     * 输入：nums = [4,2,3], k = 1
     * 输出：5
     * 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
     * 示例 2：
     *
     * 输入：nums = [3,-1,0,2], k = 3
     * 输出：6
     * 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
     * 示例 3：
     *
     * 输入：nums = [2,-3,-1,5,-4], k = 2
     * 输出：13
     * 解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
     *
     * 提示：
     *
     * 1 <= nums.length <= 104
     * -100 <= nums[i] <= 100
     * 1 <= k <= 104
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations
     */
    /**
     * 解法：排序
     * 先将数组排序，遍历数组，若当前元素是复数，并且 k 大于 0 ，当前元素反转，k --
     * 遍历结束，再次排序数组，若 k 大于 0 ，有2钟情况：
     * 1、k 是偶数，可以反转同一个元素，最终还是元素本身，不影响最终的和；
     * 2、k 是奇数，可以反转 k 次第一个元素，最终只需要减去 2 倍的第一个元素即可。
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] < 0 && k > 0){
                nums[i] = -1 * nums[i];
                k --;
            }
            sum += nums[i];
        }
        Arrays.sort(nums);
        return sum - (k % 2 == 0 ? 0 : 2 * nums[0]);
    }
}
